package Algorithms.recursion;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;

/**
 * description: 背包问题<br>
 * createTime: 2018/10/3110:34 <br>
 *
 * @author zzh
 */
public class PackagePuzzle {
    private int target;

    private List<Integer> chooseList;

    List<Integer> result;

    private boolean isFind = false;


    public PackagePuzzle(int target, List<Integer> chooseList) {
        this.target = target;
        this.chooseList = chooseList;
    }


    /**
     * isBig为true时，尽量取大的值，结果集的元素数最少
     * isBig为false时，尽量取小的值，结果集的元素数最多
     *
     * @param target
     * @param chooseList
     * @param isBig
     */
    public PackagePuzzle(int target, List<Integer> chooseList, boolean isBig) {
        this.target = target;
        this.chooseList = chooseList;
        if(isBig) {
            Collections.sort(chooseList, (val1, val2) -> val2.compareTo(val1));
        } else {
            Collections.sort(chooseList);
        }
    }

    public List<Integer> fillPackage() {
        result = new ArrayList<>();
        fillPackage(0, target);
        if(!isFind) {
            result = new ArrayList<>();
        }
        return result;
    }

    private List<Integer> fillPackage(int startIndex, int newTarget) {
        int choose = chooseList.get(startIndex);
        if(startIndex == chooseList.size() - 1) {
            if(newTarget == choose) {
                result.add(choose);
                isFind = true;
            }
            return result;
        }
        if(choose < newTarget) {
            result.add(choose);
            fillPackage(startIndex + 1, newTarget - choose);
            if(!isFind) {
                result.remove(result.size() - 1);
                fillPackage(startIndex + 1, newTarget);
            }
        } else if(choose == newTarget) {
            result.add(choose);
            isFind = true;
        } else {
            fillPackage(startIndex + 1, newTarget);
        }
        return result;
    }

    public List<Integer> getResult() {
        if(result != null) {
            return result;
        }
        return fillPackage();
    }


    public static void main(String[] args) {
        List<Integer> list = Arrays.stream("11,1,2,8,7,4,3,6,5".split(","))
                .mapToInt(s -> Integer.parseInt(s)).boxed()
                .collect(Collectors.toList());
        System.out.println(new PackagePuzzle(25, list)
                .fillPackage());

        System.out.println(new PackagePuzzle(25, list, true)
                .fillPackage());

        System.out.println(new PackagePuzzle(25, list, false)
                .fillPackage());
    }
}
